<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <div></div>
        <script>
                        // 给定一个二叉树，返回它的 后序 遍历。

                        // 示例:

                        // 输入: [1,null,2,3]
                        //    1
                        //     \
                        //      2
                        //     /
                        //    3

                        // 输出: [3,2,1]
                        // 进阶: 递归算法很简单，你可以通过迭代算法完成吗？

                        // 来源：力扣（LeetCode）
                        // 链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal
                        // 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
                        /**
                         * Definition for a binary tree node.
                         */
                        function TreeNode(val, left, right) {
                            this.val = val === undefined ? 0 : val;
                            this.left = left === undefined ? null : left;
                            this.right = right === undefined ? null : right;
                        }
                        /**
                         * @param {TreeNode} root
                         * @return {number[]}
                         */
                        var postorderTraversal = function (root) {

                        };



            //   二叉树的遍历分为广度优先搜索（BFS）和深度优先搜索（DFS）两种。
            // 实现方式一共分为7种。
            // 1、BFS
            // 层次遍历（队列）
            // 2、DFS（递归/非递归）
            // 先序遍历、中序遍历、后序遍历（栈）

            // P.S.
            // 1、修改访问函数visit即可。
            // 2、关于此题的解法，有人提出根右左（NRL）的方式先序访问，最后再逆转结果，虽然可以解决问题，但并不是真正的后序遍历，不能解决普遍问题。
            // 3、后序遍历时栈中的所有节点恰好构成了当前节点的路径。


            /**
             * Definition for a binary tree node.
             * @param {*} val
             * @param {*} left
             * @param {*} right
             */
            class TreeNode {
                constructor(val, left, right) {
                    this.val = (val === undefined ? 0 : val)
                    this.left = (left === undefined ? null : left)
                    this.right = (right === undefined ? null : right)
                }
            }

            /**
             * 层次遍历
             * @param {BiTree} T
             * @param {Function} visit
             */
            function LevelOrder(T, visit = x => console.log(x.val)) {
                if (T !== null) {
                    const queue = [];
                    queue.push(T);
                    let p;
                    while (queue.length) {
                        p = queue.shift();
                        visit(p);
                        p.left && queue.push(p.left);
                        p.right && queue.push(p.right);
                    }
                }
            }

            /**
             * 先序遍历 递归
             * @param {BiTree} T
             * @param {Function} visit
             */
            function PreOrder(T, visit = x => console.log(x.val)) {
                if (T !== null) {
                    visit(T)
                    PreOrder(T.left, visit)
                    PreOrder(T.right, visit)
                }
            }

            /**
             * 中序遍历 递归
             * @param {BiTree} T
             * @param {Function} visit
             */
            function InOrder(T, visit = x => console.log(x.val)) {
                if (T !== null) {
                    InOrder(T.left, visit)
                    visit(T)
                    InOrder(T.right, visit)
                }
            }

            /**
             * 后序遍历 递归
             * @param {BiTree} T
             * @param {Function} visit
             */
            function PostOrder(T, visit = x => console.log(x.val)) {
                if (T !== null) {
                    PostOrder(T.left, visit)
                    PostOrder(T.right, visit)
                    visit(T)
                }
            }

            /**
             * 先序遍历 非递归
             * @param {BiTree} T
             * @param {Function} visit
             */
            function PreOrder2(T, visit = x => console.log(x.val)) {
                const stack = [];
                // T && stack.push(T);
                // let p;
                // while (stack.length) {
                //     p = stack.pop();
                //     visit(p);
                //     p.right && stack.push(p.right);
                //     p.left && stack.push(p.left);
                // }
                let p = T;
                while (stack.length || p) {
                    if (p) {
                        visit(p);
                        stack.push(p)
                        p = p.left
                    } else {
                        p = stack.pop();
                        p = p.right;
                    }
                }
            }

            /**
             * 中序遍历 非递归
             * @param {BiTree} T
             * @param {Function} visit
             */
            function InOrder2(T, visit = x => console.log(x.val)) {
                const stack = [];
                let p = T;
                while (stack.length || p) {
                    if (p) {
                        stack.push(p)
                        p = p.left;
                    } else {
                        p = stack.pop();
                        visit(p);//和先序遍历就这一句不同
                        p = p.right;
                    }
                }
            }

            /**
             * 后序遍历 非递归
             * 这个遍历是最难的，关键在于出栈后右子树的处理
             * @param {BiTree} T
             * @param {Function} visit
             */
            function PostOrder2(T, visit = x => console.log(x.val)) {
                const stack = [];
                let p = T, pre = null;
                while (stack.length || p) {
                    if (p) {
                        stack.push(p)
                        p = p.left;
                    } else {
                        p = stack.pop();
                        if (!p.right || p.right === pre) {//没有右子树或刚访问过右子树
                            visit(p);
                            pre = p
                            p = null;
                        } else {//有右子树并且没有访问
                            stack.push(p);
                            stack.push(p.right);//右子树入栈
                            p = p.right.left;//转向右子树的左子树
                        }
                    }
                }
            }

            /**
             * NRL先序访问，逆转结果（非后序遍历）
             * @param {TreeNode} root
             * @return {number[]}
             */
            var postorderTraversal = function (root) {
                let ret = [],
                    stack = [], p = root;
                while (p || stack.length) {
                    if (p) {
                        ret.push(p.val);
                        stack.push(p);
                        p = p.right;
                    } else {
                        p = stack.pop();
                        p = p.left;
                    }
                }
                return ret.reverse();
            };

            /**
             * 再啰嗦几句  关于JS递归写法，后序就是把root.val放在最后
             * 先序、中序以此类推
             * @param {TreeNode} root
             * @return {number[]}
             */
            var postorderTraversal = function(root) {
                return root === null ? [] : [...postorderTraversal(root.left),...postorderTraversal(root.right),root.val]
            };

            // 作者：xi-yue-12
            // 链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/er-cha-shu-de-suo-you-bian-li-fang-fa-jian-ji-ming/
            // 来源：力扣（LeetCode）
            // 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
        </script>
    </body>
</html>
